﻿//524. 通过删除字母匹配到字典里最长单词
//给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
//如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。


class Solution {
public:
    bool isSubsequence(string s, string t)
    {
        int  i = 0, j = 0;
        for (int i = 0; i < s.size(); i++)
        {
            while (j < t.size() && t[j] != s[i])
            {
                j++;
            }
            if (j >= t.size())
            {
                return false;
            }
            j++;
        }
        return true;
    }

    string findLongestWord(string t, vector<string>& dictionary)
    {
        string ans = "";
        for (auto& s : dictionary)
        {
            if (isSubsequence(s, t))
            {
                if (ans.size() < s.size())
                {
                    ans = s;
                }
                else if (ans.size() == s.size())
                {
                    ans = ans > s ? s : ans;
                }
            }
        }
        return ans;
    }
};